package jago02.jago0201.ag02_lineTable;

import java.util.Iterator;

/**
 * 链式栈
 * 杂化简：链式栈从首节点head开始，每次将元素追加到首节点后的第一个节点，节点存储元素和下一个节点
 *
 * 解目录：
 *      1.用N表示链式栈长度，表示链式栈的元素个数
 *      2.内部类Node包含元素值和下个节点
 *      3.链式栈入栈就是新增数据节点，并追加到首节点后的第一个节点，即head.next的位置，然后N++
 *      4.链式栈出栈就是每次都移除，首节点后的第一个节点，即head.next的位置，然后N--
 * 复杂度：所有方法都是O(1)
 */
public class LineTable04_Stack<T> implements Iterable<T> {
    //节点内部类
    private class Node{
        T item;
        Node next;
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    //头节点
    private Node head;
    //链式栈长度
    private int N;
    //构造
    public LineTable04_Stack() {
        this.head = new Node(null,null);
        this.N = 0;
    }
    //链式栈判空
    public boolean isEmpty(){
        return this.N == 0;
    }
    //获取链式栈长度
    public int size(){
        return this.N;
    }
    //把元素压入栈
    public void push(T t){
        //先进后出
        //找到首节点指向的第一个节点
        Node oldFirst = this.head.next;
        //创建新节点
        Node newNode = new Node(t,null);
        //让首节点指向新节点
        this.head.next = newNode;
        newNode.next = oldFirst;
        this.N++;
    }

    public T pop(){
        //找到首节点指向的第一个节点
        Node oldFirst = this.head.next;
        if (null == oldFirst){
            return null;
        }
        this.head.next = oldFirst.next;
        this.N--;
        return oldFirst.item;
    }


    private class OneWayLinkListIterator implements Iterator{
        private Node curr;

        public OneWayLinkListIterator() {
            this.curr = head;
        }

        @Override
        public boolean hasNext() {
            return this.curr.next != null;
        }
        @Override
        public Object next() {
            curr = curr.next;
            return curr.item;
        }
    }

    @Override
    public Iterator iterator() {
        return new OneWayLinkListIterator();
    }

    public static void main(String[] args) {
        LineTable04_Stack<String> stack = new LineTable04_Stack();

        stack.push("张三");
        stack.push("李四");
        stack.push("王五");
        stack.push("老朱");
        System.out.println(stack);
        for (String str : stack) {
            System.out.print(stack.pop()+" ");
        }
    }
}
